package com.leetcode.partition1;

import java.util.*;

/**
 * @author `RKC`
 * @date 2021/8/1 9:47
 */
public class LC46全排列 {

    public static List<List<Integer>> permute(int[] nums) {
        return method2(nums);
    }

    public static void main(String[] args) {
        int[] nums = { 1, 2, 3 };
        System.out.println(permute(nums));
    }

    //标记法
    private static List<List<Integer>> method2(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        //用于记录当前所遍历的路径上是否已经有访问过的结点
        boolean[] used = new boolean[nums.length];
        backtracking(result, nums, used, new ArrayList<>(nums.length));
        return result;
    }

    private static void backtracking(List<List<Integer>> result, int[] nums, boolean[] used, List<Integer> path) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            path.add(nums[i]);
            used[i] = true;
            backtracking(result, nums, used, path);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }

    //交换法
    private static List<List<Integer>> method1(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtracking(result, 0, nums);
        return result;
    }

    private static void backtracking(List<List<Integer>> result, int index, int[] nums) {
        if (index == nums.length - 1) {
            List<Integer> item = new ArrayList<>();
            for (int num : nums) item.add(num);
            result.add(item);
            return;
        }
        for (int i = index; i < nums.length; i++) {
            swap(i, index, nums);
            backtracking(result, index + 1, nums);
            swap(i, index, nums);
        }
    }

    private static void swap(int i, int j, int[] nums) {
        if (i == j) return;
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
